package test.n00500;


import static utils.Tools.listOf;

public class Problem00550 {
    public static void main(String[] args) {
        println(new int[]{2, 3, 1, 1, 4});
        println(new int[]{3, 2, 1, 0, 4});
    }

    public static void println(int[] nums) {
        Solution ss = new Solution();
        System.out.println(listOf(nums) + "," + listOf(ss.canJump(nums)));
    }

    public static class Solution {

        /**
         * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
         * <p>
         * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
         * <p>
         * 判断你是否能够到达最后一个下标。
         * <p>
         * 解题思路:
         *
         * 贪心算法（反向查找）
         *
         * @param nums
         * @return
         */
        public boolean canJump(int[] nums) {
            int position = nums.length - 1;

            int steps = 0;
            while (position > 0) {
                for (int i = 0; i <= position; i++) {
                    if (i + nums[i] >= position) {
                        steps++;
                        position = i;
                        break;
                    }
                }

                if (steps > nums.length - 1) {
                    return false;
                }
            }
            return true;
        }
    }
}
